package leetcode;

//find the additive number.
//112358, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8;
//199100199,  1 + 99 = 100, 99 + 100 = 199
//can't exist leading-zero , like 03, 036, but 0 is admit
public class AdditiveNumber {

	public static void main(String[] args) {
		AdditiveNumber number = new AdditiveNumber();
//		System.out.println(number.isAdditiveNumber("011235"));
//		System.out.println(number.isAdditiveNumber("101123"));
//		System.out.println(number.isAdditiveNumber("11213253863101"));
		System.out.println(number.isAdditiveNumber("1023"));
		System.out.println(number.isAdditiveNumber("1203"));
//		System.out.println(number.isAdditiveNumber("211738"));
		System.out.println(number.isAdditiveNumber("0235813"));
//		System.out.println(number.isAdditiveNumber("12012"));
	}
	//这道题的思想是 首先逐个试探生成第一个和第二个数
	public boolean isAdditiveNumber(String num) {
        if(num == null || num.length() <= 2){
            //at least 3 numbers
            return false;
        }
        //the key point is find out the first and second number
        long first = 0;
        long second = 0;
        int length = num.length();
        //actually, the i range can scale to n / 2, because if equal n / 2, the last two number won't bigger than the first number
        for(int i = 0; i < length - 2; i++){
            //there are can't have leading zero
            //wrong, 0 can be the second number, so we can't continue while equal 0
            // if(num.charAt(i + 1) == '0'){
            //     continue;
            // }
        	//apparently, it's not suit to place the code in there, the one method is put in method isValid
//        	if(num.charAt(i + 1) == '0'){
//        		first = Long.parseLong(num.substring(0, i + 1));
//        		second = 0;
//        		if(isValid(first, second, i + 2, num)){
//        			return true;
//        		}else{
//        			continue;
//        		}
//        	}
            first = Long.parseLong(num.substring(0, i + 1));
            for(int j = i + 1; j < length - 1; j++){
                // if(num.charAt(j + 1)) == '0'){
                //     continue;
                // }
//            	if(num.charAt(j + 1) == '0'){
//            		first = Long.parseLong(num.substring(0, i + 1));
//            		second = 0;
//            		if(isValid(first, second, i + 2, num)){
//            			return true;
//            		}else{
//            			continue;
//            		}
//            	}
                second = Long.parseLong(num.substring(i + 1, j + 1));
                if(isValid(i, j, j + 1, num)){
                    return true;
                }
            }
        }
        return false;
    }
    
    public boolean isValid(int i, int j, int start, String num){
    	//如果前两个数不符合要求
    	if (num.charAt(0) == '0' && i >= 1){
    		return false;
    	}
    	if (num.charAt(i + 1) == '0' && j > i + 1){
    		return false;
    	}
        int length = num.length();
        //在有前缀0的时候，parseLong方法会返回去掉0的结果，这样就会返回错误的结果，比如1203，会返回true
        String sum;
        Long first = Long.parseLong(num.substring(0, i + 1));
		Long second = Long.parseLong(num.substring(i + 1, j + 1));
		System.out.println("first" + first + "Second" + second);
        for (int index = start; index < length; index += sum.length()) {
            second = second + first;
            first = second - first;
            sum = second.toString();
            if (!num.startsWith(sum, index)){
            	return false;
            }
        }
        return true;
    }
	
    //the bad idea
    public boolean isValid(long first, long second, int start, String num){
        int length = num.length();
        long cur = 0;
        int begin = start;
        for(int i = start; i < length; i++){
            if( (cur = Long.parseLong(num.substring(begin, i + 1))) == (first + second)){
                first = second;
                second = cur;
                begin = i + 1;
            } 
            else if(i == length - 1 || cur > (first + second)){
            	return false;
            }
        }
        return true;
    }
}
